# -*- mode: org; fill-column: 80; -*-
#+TITLE: Exercises
#+AUTHOR: Zelphir Kaltstahl
#+STARTUP: content
#+STARTUP: indent
#+STARTUP: align
#+STARTUP: inlineimages
#+STARTUP: entitiesplain
#+STARTUP: nologdone
#+STARTUP: nologreschedule
#+STARTUP: nologredeadline
#+STARTUP: nologrefile
#+TODO: TODO WIP | DONE
#+DATE: [2021-11-09 Tue]
#+LANGUAGE: English
#+PRIORITIES: A C C

* About
:PROPERTIES:
:CUSTOM_ID: about
:END:

This org file contains solutions to the exercises of "Elements of ML Programming" by Jeffrey D. Ullman.

* Solutions
:PROPERTIES:
:CUSTOM_ID: solutions
:END:

** 2.1.1

#+name: 2-1-1-a
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1 + 2 * 3
#+end_src

#+RESULTS: 2-1-1-a
:results:
val it = 7 : int
:end:

#+name: 2-1-1-b
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
5.0 - 4.2 / 1.4
#+end_src

#+RESULTS: 2-1-1-b
:results:
val it = 2.0 : real
:end:

#+name: 2-1-1-c
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
11 div 2 mod 3
#+end_src

#+RESULTS: 2-1-1-c
:results:
val it = 2 : int
:end:

-> ~div~ either has higher precedence than ~mod~ or is first evaluated, because it is on the left.

#+name: 2-1-1-d
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
"foo" ^ "bar" ^ ""
#+end_src

#+RESULTS: 2-1-1-d
:results:
val it = "foobar" : string
:end:

#+name: 2-1-1-e
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
3 > 4 orelse 5 < 6 andalso not (7<>8)
#+end_src

#+RESULTS: 2-1-1-e
:results:
val it = false : bool
:end:

#+name: 2-1-1-f
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
if 6 < 10 then
    6.0
else
    10.0
#+end_src

#+RESULTS: 2-1-1-f
:results:
val it = 6.0 : real
:end:

#+name: 2-1-1-g
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
0xAB+123
#+end_src

#+RESULTS: 2-1-1-g
:results:
val it = 294 : int
:end:

#+name: 2-1-1-h
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
0xAB < 123
#+end_src

#+RESULTS: 2-1-1-h
:results:
val it = false : bool
:end:

** 2.1.2

#+name: 2-1-2-a
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
8/4
#+end_src

- uses real division with integers

#+name: 2-1-2-b
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
if 2 < 3 then 4
#+end_src

- there is no ~if ... then ...~ expression in Standard ML

#+name: 2-1-2-c
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1 < 2 and 5 > 3
#+end_src

- using ~and~ as boolean operator, which it is not

#+name: 2-1-2-d
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
6 + 7 DIV 2
#+end_src

- writing ~div~ in capital letters. SML is case sensitive.

#+name: 2-1-2-e
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
4. + 3.5
#+end_src

- ~4.~ is not a complete input. It is not a real number for SML.

#+name: 2-1-2-f
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1.0 < 2.0 or 3 > 4
#+end_src

- using ~or~ as boolean operator, which it is not meant to be used for.

#+name: 2-1-2-g
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
#"a" ^ #"b"
#+end_src

- using concatenation for strings on characters

#+name: 2-1-2-h
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
123.
#+end_src

- ~123.~ is not a complete input

#+name: 2-1-2-i
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
1.0 = 2.0
#+end_src

- using ~=~ on reals, which is not allowed in SML

** 2.1.3

#+name: 2-1-3
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
print ("\"\\\\\\\" stands for the double-quote character, \\\n \
      \\\which otherwise would be interpreted \\\n \
      \\\as the string ender.\"\n")
#+end_src

#+RESULTS: 2-1-3
:results:
"\\\" stands for the double-quote character, \
 \which otherwise would be interpreted \
 \as the string ender."
val it = () : unit
:end:

** 2.1.4

#+name: 2-1-4-a
#+begin_src sml :results output verbatim replace drawer :tangle exercises.sml
val cond1 = true;
val cond2 = false;

(* andalso implementation *)
if cond1 then
    cond2
else
    false;

(* orelse implementation *)
if cond1 then
    true
else
    cond2
#+end_src

** 2.2.1

#+name: 2-2-1
#+begin_src sml :results verbatim output replace drawer
(* a *)
floor 123.45;
(* b *)
floor ~123.45;
(* c *)
ceil 123.45;
(* d *)
ceil ~123.45;
(* e *)
ord #"Y";
(* f *)
chr 120;
(* g *)
real (ord #"N");
(* h *)
chr (trunc 97.0);
(* i *)
str #"Z";
#+end_src

#+RESULTS: 2-2-1
:results:
val it = 123 : int
:end:

** 2.2.2

1. ~ceil~ should be applied to reals, not to integers. If we already have an
   integer, what is the point of applying ~ceil~?
2. The ~then~ and ~else~ branches return different types of values. A fix would
   be to return ~7~, the integer, instead of ~7.0~ the real.
3. ~chr~ can only be used on ~255~ or lower.
4. ~chr~ can only be used on numbers > 0.
5. ~ord~ can only be used on characteres. We could write the /character/ ~#"3"~
   instead.
6. ~chr~ can only be used on integers.
7. ~0~ is not a boolean value. Write an expression resulting in a boolean value
   as a condition instead of ~0~.
8. ~ord~ can only be used on characters. ~"a"~ is a string. Write the character
   ~#"a"~ instead.

** 2.3.1

Choice of:

+ alphanumeric identifier (ordinary non-type values)
+ symbolic identifier
+ type representing identifier
+ not a valid identifier

Solution:

1. ~The7Dwarves~: alphanumeric indentifier
2. ~7Dwarves~: not a valid identifier, because it starts with a digit.
3. ~SevenDwarves,The~: not a valid identifier, because it contains a ~,~, which
   cannot be part of any identifier.
4. ~'SnowWhite'~: type representing identifier
5. ~a<=b~: not a valid identifier, because it mixes symbolic identifier
   characters with alphanumeric identifier characters.
7. ~hurrah!~: not a valid identifier, because it mixes symbolic identifier
   characters with alphanumeric identifier characters.
8. ~#1~: not a valid identifier, mixing symbolic identifier characters with
   alphanumeric identifier characters.
9. ~'123~: not a valid identifier. Apparently one cannot have a digit as a first
   character after the single quote.

** 2.3.2

- ~a~, ~b~ and ~c~.

** 2.4.1

1. ~4~
2. ~3~
3. ~[4,5]~
4. ~[#"f",#"o",#"o"]~
5. ~"foo"~
6. ~["c","a","t"]~
7. ~["c","o","b","o","l"]~
8. ~"cat"~

** 2.4.2

1. accessing a position that does not exist
2. the empty list has no element in it, so there cannot be a head
3. using a list acccessor with a non-list argument
4. using ~explode~ with a non-string argument
5. using ~implode~ with non-char-list arguments
6. using ~::~ operator with two lists instead of an element and a list
7. the empty list has no tail
8. trying to use the append operator ~@~ with non-lists
9. using ~concat~ with a non-string-list

** 2.4.3

1. ~real * (string * int list)~
2. ~int list list~ (because ~nil~ is an alias for ~[]~)
3. ~(int * real) list~
4. ~char list * int list list~

** 2.4.4

1. No. Tuples have a non-variable length and as such the ML type system
   distinguishes between 2-tuples and 3-tuples. Tuples can contain elements of
   multiple types, which means that the type system needs to make sure to
   provide suficient information by mentioning the type of each element, in
   contrast to lists.
2. Yes. Lists are of variable length and the ML type system does not distinguish
   between different lengths of lists. Lists can also contain only elements of
   the same type, so having the information "int list" is sufficient for the
   type system.

** 2.4.5

1. example:

   #+begin_src sml
   [[[1]]]
   #+end_src

2. example:

   #+begin_src sml
   [(1, #"1")]
   #+end_src

3. example:

   #+begin_src sml
   (["s"], (1, (2.0, "2.5")), 3)
   #+end_src

4. example:

   #+begin_src sml
   (((1, 2), ([true]), 1.0), (2.0, "a"))
   #+end_src

5. example:

   #+begin_src sml
   ((true, 1), #"c")
   #+end_src

6. example:

   #+begin_src sml
   (1.0, [[[[1]]]])
   #+end_src

** 2.4.6

convert string of length 1 into its character

#+begin_src sml
hd(explode("a"));
#+end_src

** 3.1.1

1. code:

   #+begin_src sml
fun cube (x: real) =
    x * x * x;
   #+end_src

2. code:

   #+begin_src sml
fun min3 (a: int, b: int, c: int) =
    let
        fun min2 (a: int, b: int) =
            if a <= b
            then a
            else b;
    in
        min2 (min2 (a, b), c)
    end;

   #+end_src

   #+RESULTS:
   : val min3 = fn : int * int * int -> int

3. code:

   #+begin_src sml
fun third (lst: 'a list) =
    hd(tl(tl(lst)));
   #+end_src

   #+RESULTS:
   : val third = fn : 'a list -> 'a

4. code:

   #+begin_src sml
fun reverse_3_tup (tup: 'a * 'b * 'c) =
    (#3 tup, #2 tup, #1 tup);
   #+end_src

   #+RESULTS:
   : val reverse_3_tup = fn : 'a * 'b * 'c -> 'c * 'b * 'a

5. code:

   #+begin_src sml
fun third_char (str: string) =
    hd (
        tl (
            tl (
                explode str
            )
        )
    );
   #+end_src

   #+RESULTS:
   : val third_char = fn : string -> char

6. code:

   #+begin_src sml
fun left_shift_list (lst: 'a list) =
    tl lst @ [hd lst];
   #+end_src

   #+RESULTS:
   : val left_shift_list = fn : 'a list -> 'a list

** 3.1.2

*** 1

#+begin_src sml
fun max (a: int, b: int) =
    if a >= b then a else b;

fun min (a: int, b: int) =
    if a <= b then a else b;

fun min_max_out_of_3 (a: int, b: int, c: int) =
    [min(min(a, b), c), max(max(a, b), c)];

min_max_out_of_3 (2, 1, 3);
#+end_src

#+RESULTS:
: val max = fn : int * int -> int

*** 2

**** Quicksort

First consider quicksort implemented in Scheme (taken and improved readability
from [[https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Scheme]] (2021-07-04)):

#+begin_src scheme
(define split-by
  (λ (lst pivot-test partitions-processor)
    ;; loop over elements, recursively partitioning into
    ;; elements, which satisfy the pivot-test and elements,
    ;; which do not satisfy the pivot-test.
    (let loop ([low '()] [high '()] [lst lst])
      (cond
       [(null? lst)
        ;; TODO: Might be able to simply use the empty list
        ;; here, instead of applying the
        ;; partitions-processor.
        (partitions-processor low high)]
       [(pivot-test (car lst))
        ;; Collect element satisfying the pivot-test.
        (loop low
              (cons (car lst) high)
              (cdr lst))]
       [else
        ;; Collect element not satisfying the pivot-test.
        (loop (cons (car lst) low)
              high
              (cdr lst))]))))

(define quicksort
  (λ (lst greater-than?)
    (cond
     [(null? lst) '()]
     [else
      (split-by
       ;; Use only the rest of the list, as the first
       ;; element is used as pivot element.
       (cdr lst)
       ;; Predicate for determining whether an element is
       ;; greater than the pivot element. Here naive
       ;; approach of using the first element as a pivot
       ;; element.
       (λ (x) (greater-than? x (car lst)))
       ;; Lambda processing partitions. What to do with the
       ;; 2 partitions after partitioning using the
       ;; greater-than? predicate as pivot-test.
       (λ (low high)
         ;; Careful: append has O(n) runtime.
         (append
          ;; recursive call for lesser elements
          (quicksort low greater-than?)
          ;; pivot element
          (list (car lst))
          ;; recursive call for greater elements
          (quicksort high greater-than?))))])))


(define (quicksort-2 lst gt?)
  (if (null? lst)
      '()
      (append (quicksort (filter (lambda (x) (gt? (car lst) x)) (cdr lst))
                         gt?)
              ;; needs to be a list for append to work
              (list (car lst))
              (quicksort (filter (lambda (x) (not (gt? (car lst) x))) (cdr lst))
                         gt?))))
#+end_src

We can rewrite this in SMLNJ:

#+name: quicksort
#+begin_src sml
fun quicksort (nil,
               greater_than: 'a * 'a -> bool,
               partition_pivot_not_pivot: 'a list -> 'a * 'a list) = nil
  | quicksort (lst: 'a list,
               greater_than: 'a * 'a -> bool,
               partition_pivot_not_pivot: 'a list -> 'a * 'a list) =
    let
        val (pivot_elem, not_pivot_elems) = partition_pivot_not_pivot lst;
    in
        let
            val (low, high) = List.partition (fn x => greater_than(x, pivot_elem)) not_pivot_elems;
        in
            quicksort(low, greater_than, partition_pivot_not_pivot)
            @
            [pivot_elem]
            @
            quicksort(high, greater_than, partition_pivot_not_pivot)
        end
    end;
#+end_src

**** Solution

And then we can use it as follows:

#+begin_src sml
<<quicksort>>

fun sorted_triple (a: int, b: int, c: int) =
    quicksort ([a,b,c],
               (fn (a, b) => a > b),
               (fn lst => (hd lst, tl lst)));
#+end_src

*** 3

#+begin_src sml
fun round_tenth (num: real) =
    Real.fromInt(round(num * 10.0)) / 10.0;
#+end_src

*** 4

#+begin_src sml
fun delete_second (lst: 'a list) =
    if length(lst) >= 2
    then
        let
            val (a::b::rest) = lst;
        in
            a :: rest
        end
    else
        lst;
#+end_src

** 3.1.3

*** 1

8

*** 2

11

*** 3

8

*** 4

10

*** 5

18

*** 6

17

** 3.2.1

*** 1

#+begin_src sml
fun fac 0 = 1
  | fac 1 = 1
  | fac n =
    let
        fun iter 1 prod = prod
          | iter remaining_factors prod =
            iter (remaining_factors - 1) (prod * remaining_factors);
    in
        if n > 0
        then iter n 1
        else raise Fail "n must be 0 or greater"
    end;
#+end_src

*** 2

#+begin_src sml :results output verbatim drawer replace
fun cycle (lst: 'a list, i: int) =
    let
        fun left_shift_list (lst: 'a list) =
            tl lst @ [hd lst];
    in
        if i > 0
        then
            cycle (left_shift_list(lst), (i - 1))
        else
            lst
    end;

cycle ([1,2,3,4,5], 3);
#+end_src

#+RESULTS:
:results:
val cycle = fn : 'a list * int -> 'a list
:end:

*** 3

#+begin_src sml :results output verbatim drawer replace
fun duplicate_elements_of_list (lst: 'a list) =
    if null(lst)
    then []
    else
        let
            val first = hd lst;
        in
            first :: first :: duplicate_elements_of_list (tl lst)
        end;

duplicate_elements_of_list [1,2,3,4];
#+end_src

#+RESULTS:
:results:
val duplicate_elements_of_list = fn : 'a list -> 'a list
:end:

*** 4

#+begin_src sml :results output verbatim drawer replace
fun len (lst: 'a list) =
    if null lst
    then
        0
    else
        1 + len(tl(lst));
#+end_src

*** 5

#+begin_src sml :results output verbatim drawer replace
fun pow (base: real, exponent: int) =
    let
        fun iter (base: real, exponent: int, product: real) =
            if exponent = 1
            then product * base
            else iter (base, (exponent - 1), (product * base));
    in
        if exponent = 0
        then 1.0
        else iter (base, exponent, 1.0)
    end;

pow (8.5, 3);
#+end_src

*** 6

#+begin_src sml :results output verbatim drawer replace
fun find_largest (lst: real list) =
    foldl (fn (elem, prev) => if elem > prev
                              then elem
                              else prev)
          Real.negInf
          lst;

find_largest [
    2.0,
    7456.0,
    3.0,
    878.0,
    2346.0,
    8768.0,
    2.0,
    2.0,
    42.0,
    767.0,
    8768.0,
    35.0,
    32.0,
    423.0,
    92346.0
];
#+end_src

#+RESULTS:
:results:
val find_largest = fn : real list -> real
:end:

** 3.2.2

*** 1

#+begin_src sml :results output verbatim drawer replace
fun foo (a,b,c,d) =
    if a = b
    then c + 1
    else
        if a > b
        then c
        else
            b + d;
#+end_src

1. The return types of all branches must agree. So if one branch returns an integer, all branches must return an integer.
2. For overloaded operators like ~+~, the operands need to have the same type. If one operand is an integer, then so must the other be.
3. The branch ~then c + 1~ returns an integer, because ~1~ is an integer and thus ~c~ must be an integer and the operator ~+~ for integers returns and ~int~.
4. Subsequently all other branches must return ~int~.
5. The branch ~else b + d~ must return an ~int~ as well. ~b + d~ will only return an ~int~, if ~b~ and ~d~ are both ~int~.
6. The ~=~ operator can only compare numbers of same type and not of type ~real~.
7. Since we already know the type of ~b~ to be ~int~, ~a~ must also be an ~int~.

** 3.2.3

#+begin_src sml :results output verbatim drawer replace
fun f (a: int, b, c, d, e) = ...
#+end_src

*** 1

#+begin_src sml :results output verbatim drawer replace
if a < b + c then d else e
#+end_src

- a: int
- b: int
- c: int
- d and e of same type
- f returns value of same type as d and e

*** 2

#+begin_src sml :results output verbatim drawer replace
if a < b then c else d
#+end_src

- a: int
- b: int
- c and d have same type
- e is unused and of unknown type
- f returns value of same type as c and d

*** 3

#+begin_src sml :results output verbatim drawer replace
if a < b then b + c else d + e
#+end_src

- a: int
- b: int
- c: int
- d: int
- e: int
- f returns int

*** 4

#+begin_src sml :results output verbatim drawer replace
if a < b then b < c else d
#+end_src

- a: int
- b: int
- c: int
- d: bool
- e is unused and of unknown type
- f returns bool

*** 5

#+begin_src sml :results output verbatim drawer replace
if b < c then a else c + d
#+end_src

- a: int
- b: int
- c: int
- d: int
- e is unused and of unknown type
- f returns int

*** 6

#+begin_src sml :results output verbatim drawer replace
if b < c then d else e
#+end_src

- a: int
- b: int
- c: int
- d and e of same type
- f returns value of same type as d and e have

*** 7

#+begin_src sml :results output verbatim drawer replace
if b < c then d + e else d * e
#+end_src

- a: int
- b and c of same type (implementation assumes ~int~, as long as ~real~ is not specified explicitly as type of the arguments of the function.
- d and e of same type
- f returns value of same type as d and e have

** 3.2.4

*** 1

#+begin_src sml :results output verbatim drawer replace
fun fac 0 = 1
  | fac 1 = 1
  | fac n =
    let
        fun iter 1 prod = prod
          | iter remaining_factors prod =
            iter (remaining_factors - 1) (prod * remaining_factors);
    in
        if n > 0
        then iter n 1
        else raise Fail "n must be 0 or greater"
    end;
#+end_src

At each iteration ~remaining_factors~ is reduced by ~1~ and ~prod~ multiplied by ~remaining_factors~. The environment does not really change anything else than that, because the stack frame is reused due to tail call opimization. When all is done, ~prod~ is returned and the stack frame cleaned up.

*** reverse

**** reverse using pattern matching (recommended)

#+begin_src sml
fun reverse nil = nil
  | reverse (x::xs) =
    reverse (xs) @ [x];
#+end_src

**** reverse using null predicate

#+begin_src sml
fun reverse2 (lst: 'a list) =
    if null(lst)
    then nil
    else
        reverse2 (tl(lst)) @ [hd(lst)];
#+end_src

**** alternative

#+begin_src sml
fun reverse3 nil = nil
  | reverse3 (lst: 'a list) =
    let
        fun reverse_helper (lst, acc) =
            if null(lst)
            then acc
            else reverse_helper (tl (lst), hd (lst) :: acc);
    in
        reverse_helper(lst, nil)
    end;
#+end_src

**** reverse using foldl

This is actually doing the same as ~reverse3~ above, but perhaps more elegant.

#+begin_src sml
fun reverse4 nil = nil
  | reverse4 (lst: 'a list) =
    (* cannot call foldl with tuple notation, have to call it with curried notation *)
    foldl op:: nil lst;
#+end_src

*** make a long list

#+begin_src sml
fun range (i: int) =
    if i = 0
    then nil
    else i :: range (i - 1);
#+end_src

*** merge two sorted lists into a sorted list

#+begin_src sml
fun merge (nil, nil) = nil
  | merge (lst1, nil) = lst1
  | merge (nil, lst2) = lst2
  | merge (lst1 as x::xs, lst2 as y::ys) =
    if y < x
    then y :: merge(lst1, ys)
    else x :: merge(xs, lst2);
#+end_src

** 3.3.1

*** a

This solution already uses 3 patterns, which are simple numbers or arbitrary things.

#+begin_src sml
fun fac 0 = 1
  | fac 1 = 1
  | fac n =
    let
        fun iter 1 prod = prod
          | iter remaining_factors prod =
            iter (remaining_factors - 1) (prod * remaining_factors);
    in
        if n > 0
        then iter n 1
        else raise Fail "n must be 0 or greater"
    end;
#+end_src

*** b

#+name: printer
#+begin_src sml :noweb yes :results output verbatim drawer replace
datatype primitives_wrapper =
         Int of int | Real of real | String of string

datatype compound_wrapper =
         IntList of int list |
         RealList of real list |
         StringList of string list;

fun int_list_to_string lst =
    String.concatWith ", " (map (fn num => Int.toString(num)) lst);

fun real_list_to_string lst =
    String.concatWith ", " (map (fn num => Real.toString(num)) lst);

fun string_list_to_string lst =
    String.concatWith ", " ((map (fn str => "\"" ^ str ^ "\"") lst));

fun myprint (lst: compound_wrapper) =
    case lst of
        IntList lst => print("[" ^ (int_list_to_string lst) ^ "]" ^ "\n")
      | RealList lst => print("[" ^ (real_list_to_string lst) ^ "]" ^ "\n")
      | StringList lst => print("[" ^ (string_list_to_string lst) ^ "]" ^ "\n");
#+end_src

#+begin_src sml :noweb yes :results output verbatim drawer replace
fun left_shift_list nil = nil
  | left_shift_list (x::xs) =
    xs @ [x];
#+end_src

#+RESULTS:
:results:
val left_shift_list = fn : 'a list -> 'a list
:end:

*** c

#+begin_src sml :results output verbatim drawer replace
fun left_shift_list nil = nil
  | left_shift_list (x::xs) =
    xs @ [x];

fun cycle (nil, i: int) = nil
  | cycle (x::nil, i: int) = [x]
  | cycle (xs, 0) = xs
  | cycle (xs, i: int) =
    if i > 0
    then
        cycle (left_shift_list(xs), (i - 1))
    else
        xs;
#+end_src

#+RESULTS:
:results:
val cycle = fn : 'a list * int -> 'a list
:end:

*** d

#+begin_src sml :results output verbatim drawer replace
fun duplicate_elements nil = nil
  | duplicate_elements (x::xs) =
    x :: x :: duplicate_elements(xs);
#+end_src

#+RESULTS:
:results:
val cycle = fn : 'a list * int -> 'a list
:end:

*** e

The optimal solution would be something like the following:

#+begin_src sml :results output verbatim drawer replace
fun expt (0.0, i: int) = 0.0
  | expt (1.0, i: int) = 1.0
  | expt (x: real, 0) = 1.0
  | expt (x: real, 1) = x
  | expt (x: real, i: int) =
    let
        fun iter (base: real, exponent: int, product: real) =
            if exponent = 1
            then
                product * base
            else
                iter (base, (exponent - 1), (product * base));
    in
        iter (x, i, 1.0)
    end;
#+end_src

However, pattern matching on reals like that does not work, because reals are not an equal type, a type, which can be compared using equal. So one has to take the x as is and leave those cases away:

#+begin_src sml :results output verbatim drawer replace
fun expt (x, 0) = 1.0
  | expt (x, 1) = x
  | expt (x, i) =
    let
        fun iter (base: real, exponent: int, product: real) =
            if exponent = 1
            then
                product * base
            else
                iter (base, (exponent - 1), (product * base));
    in
        iter (x, i, 1.0)
    end;
#+end_src

#+RESULTS:
:results:
val expt = fn : real * int -> real
:end:

*** f

#+begin_src sml :results output verbatim drawer replace
fun find_max xs =
    let
        fun iter (nil, x) = x
          | iter (x::xs, prev_max) =
            if x > prev_max
            then
                iter (xs, x)
            else
                iter (xs, prev_max);
    in
        iter (xs, Real.negInf)
    end;
#+end_src

** 3.3.2

#+begin_src sml :results output verbatim drawer replace
fun flip_pairs (x1::x2::xs) = x2 :: x1 :: flip_pairs(xs)
  | flip_pairs (x::nil) = x :: nil
  | flip_pairs nil = nil;
#+end_src

** 3.3.3

#+begin_src sml :results output verbatim drawer replace
fun remove_nth_member (nil, n) = nil
  | remove_nth_member (x::xs, 0) = xs
  | remove_nth_member (x::xs, n) =
    if n = 0
    then
        xs
    else
        x :: remove_nth_member (xs, (n - 1));
#+end_src

#+RESULTS:
:results:
val remove_nth_member = fn : 'a list * int -> 'a list
:end:

** 3.3.4

#+begin_src sml :results output verbatim drawer replace
(1) fun sumLists(nil) = 0
(2)   | sumLists(nil::YS) = sumLists(YS)
(3)   | sumLists((x::xs)::YS) = x + sumLists(xs::YS);

sumLists([[1, 2], nil, [3]])

-> case 3: x = 1, xs = [2], YS = [nil, [3]]
-> 1 + sumLists([[2], nil, [3]])
-> case 3: x = 2, xs = nil, YS = [nil, [3]]
-> 1 + 2 + sumLists([nil, nil, [3]])
-> case 2: YS = [nil, [3]]
-> 1 + 2 + sumLists([nil, [3]])
-> case 2: YS = [[3]]
-> 1 + 2 + sumLists([[3]])
-> case 3: x = 3, xs = nil, YS = nil
-> 1 + 2 + 3 + sumLists(nil)
-> case 1:
-> 1 + 2 + 3 + 0
-> 6
#+end_src

** 3.3.5

*** a

#+begin_src sml :results output verbatim drawer replace
(* pattern was given as: (x::y::zs, w) *)
(["a", "b", "c"], ["d", "e"])
(*
->
x = "a",
y = "b",
zs = ["c"],
w = ["d", "e"]
,*)
#+end_src

*** b

#+begin_src sml :results output verbatim drawer replace
(* pattern was given as: (x::y::zs, w) *)
(["a", "b"], 4.5)
(*
->
x = "a",
y = "b",
zs = nil,
w = 4.5
,*)
#+end_src

*** c

#+begin_src sml :results output verbatim drawer replace
(* pattern was given as: (x::y::zs, w) *)
([5], [6, 7])
(* -> does not match *)
#+end_src

* 3.3.6

#+begin_src sml
[(x,y),zs]

[,] __ zs
   |
   |__ (,) __ y
          |
          |__ x

[,] __ nil
   |
   |__ (,) __ 3
          |
          |__ (1,2)
#+end_src

* 3.3.7

#+begin_src sml
open IntInf;

fun square 0 = 0
  | square n =
    (square (n - 1)) + (2 * n) - 1;
#+end_src

* 3.3.8

#+begin_src sml
fun sort_pairs nil = nil
  | sort_pairs ((pair as (elem1, elem2)) :: nil) =
    if elem1 > elem2
    then (elem2, elem1) :: nil
    else pair :: nil
  | sort_pairs ((pair as (elem1, elem2)) :: pairs) =
    if elem1 > elem2
    then (elem2, elem1) :: sort_pairs pairs
    else pair :: sort_pairs pairs;
#+end_src

* 3.3.9

#+name: vowel_functions
#+begin_src sml :noweb yes
fun is_vowel c =
    let
        val vowels = [
            #"a", #"e", #"i", #"o", #"u", #"A", #"E", #"I", #"O", #"U"
        ];
    in
        case List.find (fn elem => elem = c) vowels
         of
            SOME c => true
          | NONE => false
    end;

fun starts_with_vowel nil = false
  | starts_with_vowel (chars: char list as (c::_)) =
    is_vowel c;
#+end_src

* 3.3.10

#+name: list_procs
#+begin_src sml
fun take_until pred nil = []
  | take_until pred (x::xs) =
    if pred x
    then []
    else x :: (take_until pred xs);

fun drop_until pred nil = []
  | drop_until pred (lst as (x::xs)) =
    if pred x
    then
        lst
    else
        drop_until pred xs;
#+end_src

#+name: string_procs
#+begin_src sml
<<list_procs>>

fun string_take_until char_pred str =
    let
        val chars = String.explode str;
    in
        String.implode (take_until char_pred chars)
    end;

fun string_drop_until char_pred str =
    let
        val chars = String.explode str;
    in
        String.implode (drop_until char_pred chars)
    end;
#+end_src

#+begin_src sml
<<vowel_functions>>
<<string_procs>>

fun pig_latin "" = ""
  | pig_latin word =
    if starts_with_vowel (String.explode word)
    then
        word ^ "yay"
    else
        let
            val non_vowel_prefix = string_take_until is_vowel word;
            val vowel_and_rest_suffix = string_drop_until is_vowel word;
        in
            vowel_and_rest_suffix ^
            non_vowel_prefix ^
            "ay"
        end;
#+end_src

* 3.3.11 - representation of sets as single linked lists

#+name: set_procs
#+begin_src sml :noweb yes
fun member (item, nil) = false
  | member (item, x::xs) =
    item = x orelse member (item, xs);

fun delete (item, nil) = []
  | delete (item, x::xs) =
    if item = x
    then xs
    else x :: delete (item, xs);

fun insert (item, nil) = [item]
  | insert (item, lst as x::xs) =
    if item = x
    then lst
    else x :: insert (item, xs);
#+end_src

* 3.3.12 - prepend to all sublists

#+begin_src sml
fun prepend_to_all (elem, nil) = []
  | prepend_to_all (elem, l::ls) =
    (elem :: l) :: (prepend_to_all (elem, ls));
#+end_src

* 3.3.13 - powerset

#+begin_src sml :noweb yes
fun prepend_to_all (elem, nil) = []
  | prepend_to_all (elem, l::ls) =
    (elem :: l) :: (prepend_to_all (elem, ls));

(* my first working solution *)
fun powerset lst =
    let
        fun iter (acc, nil) = acc
          | iter (acc, remaining as x::xs) =
            iter (acc @ (prepend_to_all (x, acc)), xs);
    in
        iter ([[]], lst)
    end;

(* shorter version which the book meant to hint at *)
fun powerset (x::xs) =
    prepend_to_all (x, (powerset xs)) @ (powerset xs)
  | powerset nil = [[]];
#+end_src

* 3.3.14 - products of differences

#+begin_src sml
fun product_of_differences (a, nil) = a
  | product_of_differences (a, lst) =
    (* using foldl to do 2 things in one pass over the list *)
    foldl (fn (b, accumulated) => accumulated * (a - b))
          1.0
          lst;

(* not sure what to name this function *)
fun unnamed_func nil = 1.0
  | unnamed_func (x::nil) = 1.0
  | unnamed_func (x::xs) =
    product_of_differences (x, xs);
#+end_src

* 3.3.15 - is empty list?

#+begin_src sml
fun is_empty nil = true
  | is_empty _ = false;
#+end_src

#+RESULTS:
: val is_empty = fn : 'a list -> bool

* 3.3.16 - deduction of inference

The given function:

#+begin_src sml
fun sumPairs nil = 0
  | sumPairs ((x,y)::zs) = x + y + (sumPairs zs);
#+end_src

+ ML infers the result type from the first pattern, where the result is the integer 0. All pattern matching branches must have the same result type, so the return type of the function must be ~int~.
+ Only integers add up to integers. Reals do only add up to reals and other types do not add up to ~int~ either.
+ To fulfill the condition, that all pattern matching branches must have the same result type, the addition of ~x + y + (sumPairs zs)~ must consist of integers.
+ This means, that ~x~ and ~y~ must be of type ~int~.
+ ~x~ and ~y~ are captured in the pattern ~((x,y)::zs)~.
+ This means, that at least at the beginning of the list, there must be a tuple of ~(x,y)~, which are of type ~int~.
+ The function assumes, that this remains true for all subsequent recursive calls.
+ In ML it is not possible to create a list, which consists of elements of inequal types.
+ If the first element of the list is a 2-tuple of elements of type ~int~, then so must the rest of the list be.

* 3.3.x - split and merge

#+name: split
#+begin_src sml :noweb yes
fun split nil = (nil, nil)
  | split [a] = ([a], nil)
  | split (a::b::cs) =
    let
        val (M, N) = split cs;
    in
        (a::M, b::N)
    end;
#+end_src

#+RESULTS:
: val split = fn : 'a list -> 'a list * 'a list

#+name: merge
#+begin_src sml :noweb yes
(* merge 2 already sorted lists *)
fun merge less (nil, M) = M
  | merge less (N, nil) = N
  | merge less (L1 as x::xs, L2 as y::ys) =
    if less (x, y)
    then x :: merge less (xs, L2)
    else y :: merge less (L1, ys);
#+end_src

#+RESULTS: merge
: val merge = fn : int list * int list -> int list

#+name: merge_sort
#+begin_src sml :noweb yes
<<split>>
<<merge>>

fun merge_sort less nil = nil
  | merge_sort less [a] = [a]
  | merge_sort less lst =
    let
        (* split list in partitions of elements of alternating indices *)
        val (part1, part2) = split lst;
        (* sort parts in recursive calls *)
        val sorted_part1 = merge_sort less part1;
        val sorted_part2 = merge_sort less part2;
    in
        merge less (sorted_part1, sorted_part2)
    end;
#+end_src

#+RESULTS: merge_sort
: val split = fn : 'a list -> 'a list * 'a list

* 3.4.1 - exponentiation function

#+begin_src sml
open IntInf;

fun expt_by_1000 0 = 0
  | expt_by_1000 1 = 1
  | expt_by_1000 x =
    let
        fun iter (accumulated, exponent) =
            if exponent < 2
            then accumulated * x
            else iter (accumulated * x, exponent - 1);
    in
        iter (1, 1000)
    end;
#+end_src

* 3.4.2

#+begin_src sml
fun split nil = (nil, nil)
  | split [a] = ([a], nil)
  | split (a::b::cs) =
    let
        val left_and_right = split cs;
    in
        (a::(#1 left_and_right), b::(#2 left_and_right))
    end;
#+end_src

#+RESULTS:
: val split = fn : 'a list -> 'a list * 'a list

* 3.4.3 - powerset improved

#+begin_src sml
fun prepend_to_all (elem, nil) = []
  | prepend_to_all (elem, l::ls) =
    (elem :: l) :: (prepend_to_all (elem, ls));

(* shorter version which the book meant to hint at *)
fun powerset nil = [[]]
  | powerset (x::xs) =
    let
        val ps = powerset xs;
    in
        prepend_to_all (x, ps) @ ps
    end;
#+end_src

* 3.4.4 - maximum improved

There is no useful place to put a ~let~ in here:

#+begin_src sml
fun find_largest (lst: real list) =
    foldl (fn (elem, prev) => if elem > prev
                              then elem
                              else prev)
          Real.negInf
          lst;
#+end_src

* 3.4.5 - x^(2^i)

#+begin_src sml
fun expt2_expti (x, i) =
    let
        fun iter (acc, x, 0) = acc
          | iter (acc, x, i) =
            iter (acc * Math.pow (x, 2.0), x, i-1);
    in
        iter (1.0, x, i)
    end;

expt2_expti (2.0, 4);
#+end_src

* 3.4.6 - alternative sum pairs

#+begin_src sml
fun sum_pairs nil = (0, 0)
  | sum_pairs ((x, y)::zs) =
    let
        val (rest_odds_sum, rest_evens_sum) = sum_pairs zs;
    in
        (x + rest_odds_sum, y + rest_evens_sum)
    end;
#+end_src

* 3.4.7 - sums of even and odd positions

#+begin_src sml
fun sum_even_odd nil = (0, 0)
  | sum_even_odd (x::nil) = (x, 0)
  | sum_even_odd (a::b::lst) =
    let
        val (a_next, b_next) = sum_even_odd lst;
    in
        (a + a_next, b + b_next)
    end;
#+end_src

* 3.5.1 - concatenate lists

#+begin_src sml
fun cat (nil, nil) = nil
  | cat (nil, lst2) = lst2
  | cat (lst1, nil) = lst1
  | cat (x::xs, ys) =
    x :: cat (xs, ys);
#+end_src

* 3.5.2 - cycle - linear time

#+begin_src sml
(* WITH CONTINUATIONS *)

fun split_cycled_and_remaining (nil, count_to_take) = (nil, nil)
  | split_up (lst, count_to_take) =
    let
        fun iter (nil, count_to_take, collect) = collect (nil, nil) (* PART1: Giving nil to the collector. *)
          (* If there are still elements in the list ... *)
          | iter ((x::xs), count_to_take, collect) =
            (* ... and the list is supposed to be cycled by more elements ... *)
            if count_to_take > 0
            then
                iter (xs,
                      count_to_take - 1,
                      (* + Wrap the collector in a new lambda expression, to
                           make a new collector.
                         + The new collector uses the result of the old collector.
                         + The old collector is given the arguments of the next
                           call, so that these are used before the current ones. *)
                      (fn (next_taken_elem, remaining_elems) =>
                          (* cons the current element in from of the result
                           from the previous collector *)
                          let
                              val (taken, rest) = collect (next_taken_elem, remaining_elems);
                          in
                              (* TODO: List is in wrong order. How to reverse without cost? *)
                              ((x :: taken), rest)
                          end))
            else
                collect (nil, x::xs)
    in
        iter (lst,
              count_to_take,
              (* Initial continuation / collect function. This one will be the
                 last to be called. It will be wrapped by other lambdas during
                 processing the list. It being called last means, that one has
                 to give it nil, to finish building lists. See PART1.*)
              (fn (taken, rest) => (taken, rest)))
    end;


fun cycle (lst, 0) = lst
  | cycle (nil, count) = nil
  | cycle (lst, count) =
    let
        val (rev_cycle_elems, remaining) = split_cycled_and_remaining (lst, count);
    in
        remaining @ (rev rev_cycle_elems)
    end;


(* OTHER SOLUTION *)

(* I found the following solution online at
<https://github.com/frutiger/emlp/blob/master/3.5/3.5.2.sml>, however, without
my comments, it is completely unreadable and ultimately it is not so great,
because it does unnecessary work. Made me lose some time figuring out, whether
this solution has any great insights, but apparently it has none. *)

fun cycle3 (nil, nil, ys) = ys
  (* If there are no more reversed elements to be cycled, reverse the reversed
     rest of the original list. This seems to be a bit of a silly step to do, as
     they were only reversed in phase 2, to now be reversed again. >.<' *)
  | cycle3 (x2r::x2rs, nil, ys) =
    cycle3 (x2rs, nil, x2r::ys)
  (* If there are more reversed elements to be cycled reverse them to correct
     order and build up the resulting list. *)
  | cycle3 (x2rs, x1r::x1rs, ys) = cycle3 (x2rs, x1rs, x1r::ys)

(* Phase 2: "Collect the rest of the original list."
   Called as follows:
   (arg 1) remaining elements of original list
   (arg 2) initially empty list
   (arg 3) accumulated elements, which shall be cycled *)
fun cycle2 (nil,     x2rs, x1rs) =
    (* If the original list has no more elements, go to phase 3.
       Calling as follows:
       (arg 1) reversed rest of original list
       (arg 2) reversed elements to be cycled
       (arg 3) initially empty list *)
    cycle3 (x2rs, x1rs, nil)
  (* If the original list has more elements, ... *)
  | cycle2 (x2::x2s, x2rs, x1rs) =
    (* ... accumulate them as well in reversed order, until no more elements are
       left. At that point we have runtime of O(n) already. The algorithm cannot
       have better worst case time complexity than O(n). *)
    cycle2 (x2s, x2::x2rs, x1rs);

(* Phase 1: "Accumulate the elements to be cycled according to the counter and
   original list." *)
fun cycle1 (x2s, x1rs, 0) =
    (* If the number of to cycle elements has reached zero, enter the second
       phase - The result of the first phase is, that all elements, which should
       be cycled, are accumulated in reversed order in x1rs. *)
    cycle2 (x2s, nil, x1rs)
  | cycle1 (x::x2s, x1rs, n) =
    (* If there are still elements in the list, which shall be cycled ... *)
    (* ... cons the head of the original list onto the accumulated list. This
       reverses the order of elements found in the original list. Continue with
       the counter reduced by 1. *)
    cycle1 (x2s, x::x1rs, n - 1)
  | cycle1 (nil, x1rs, n) =
    (* If there is no remaining element, but still elements should be cycled,
       return the empty list. -- Is this a coorect idea? Why not cycle elements
       more than once, if there are insufficient elements? Would that not be a
       more natural cycling algorithm? *)
    nil;

(*
 ,* x1s : list of elements to cycle
 ,* n   : number of shifts to make
 ,*)
fun cycle (x1s, n) =
    (* original list goes into the first slot *)
    cycle1 (x1s, nil, n);

(* Considering, that I have not found a good solution online, I wonder, what the
actual by the author intended solution was. Did the exercise have 2 exclamation
marks, because of the way one might need to use continuations? Because of how it
involves multiple steps? Or did it have 2 exclamation marks, because the
solution is even more difficult to find, than the one with continuations? *)
#+end_src

* 3.6.* Polynomials

#+begin_src sml
  structure Polynomial = struct
      type CoefficientsList = real list;
      fun add P nil = P
        | add nil Q = Q
        | add ((p:real)::ps) (q::qs) =
          (p + q) :: (add ps qs);

      fun scalar_multiply nil scalar = nil
        | scalar_multiply ((p:real)::ps) scalar =
          (p * scalar) :: (scalar_multiply ps scalar);

      (* The coefficients of lowest exponents come first by
      convention. Prepending a 0.0 will move all coefficients
      to positions of coefficients of the next higher
      exponents. *)
      fun shift_increasing P = 0.0 :: P;

      fun shift P 0 = P
        | shift P n = shift_increasing (shift P (n - 1));

      fun multiply P nil = nil
        | multiply P (q::qs) =
          add
              (* Start calculating with the coefficient of the
              lowest exponent. At the beginning, this will be
              the coefficient for x^0. For x^0 only the
              coefficient remains, because x^0 = 1. For later
              iterations, the result will be shifted by 1
              position to account for the higher exponent. *)
              (scalar_multiply P q)
              (*

              The next iteration will create a result for the
              next higher exponent. This fact is taken into
              account here, by shifting the result of the
              recursive call by 1 position, before adding it
              to the complete result of the computation.

              At each iteration, we increase the shift by 1,
              which makes sense, because the list of
              coefficients representing a polynomial is
              complete from lowest exponent position to
              highest exponent position. For example when we
              multiply with the coefficient of x^1, the shift
              will be 1. Then when we multiply with the
              coefficient of x^2 the result will be shifted by
              2. As a result we get the coefficients at the
              correct positions.

              ,*)
              (shift_increasing
                   (* Calculate the result for the coefficient
                   of the next exponent. *)
                   (multiply P qs));

      fun substract P nil = P
        | substract P Q =
          add P (scalar_multiply Q ~1.0);

      fun length P = List.length P;
  end;
#+end_src

** Karatsuba-Ofman

There is some mathematical stuff in the book leading to the implementation of Karatsuba-Ofman algorithm.

#+begin_src sml
  structure KaratsubaOfman = struct
      exception UnsuitablePolynomial;

      fun best_split n m =
          (* If n is less than or equal to half of m, then use n. (Use the much smaller one.) *)
          if 2 * n <= m then n
          (* If m is less than or equal to half of n, then use m. (Use the much smaller one.) *)
          else if 2 * m <= n then m
          (* If n is less or equal to m, take half of m. *)
          else if n <= m then m div 2
          (* n/2 < m < n*)
          else n div 2;

      fun carve nil 0 = (nil, nil)
        | carve nil n = raise UnsuitablePolynomial
        | carve (P: Polynomial.CoefficientsList) 0 = (nil, P)
        | carve ((p::ps): Polynomial.CoefficientsList) n =
          let
              val (qs,rs) = carve ps (n-1);
          in
              (p::qs, rs)
          end;

      fun karatsuba_ofman_multiply P nil = nil
        | karatsuba_ofman_multiply nil Q = nil
        | karatsuba_ofman_multiply P (q::nil) = Polynomial.scalar_multiply P q
        | karatsuba_ofman_multiply (p::nil) Q = Polynomial.scalar_multiply Q p
        | karatsuba_ofman_multiply P Q =
          let
              val n = Polynomial.length P;
              val m = Polynomial.length Q;
              val s = Polynomial.best_split n m;
              val (T, U) = carve P s;
              val (V, W) = carve Q s;
              val TV = karatsuba_ofman_multiply T V;
              val UW = karatsuba_ofman_multiply U W;
              val TUVW = karatsuba_ofman_multiply (Polynomial.add T U) (Polynomial.add V W);
              val middle = Polynomial.substract (Polynomial.substract TUVW TV) UW;
          in
              Polynomial.add
                  (Polynomial.add
                       TV
                       (Polynomial.shift middle s))
                  (Polynomial.shift UW (2*s))
          end;
  end;
#+end_src

** 3.6.1 - genPoly

#+begin_src sml
  fun gen_poly 0 = nil
    | gen_poly n =
      1.0 :: (gen_poly (n - 1));

  (* Differences start to be visible when making polynomials with 2000
  coefficients. *)

  KaratsubaOfman.karatsuba_ofman_multiply (gen_poly 1000) (gen_poly 1000);
  Polynomial.multiply (gen_poly 2000) (gen_poly 2000);
#+end_src

** 3.6.2 - use naive multiply for low count of exponents

#+begin_src sml
  fun karatsuba_ofman_multiply P nil = nil
    | karatsuba_ofman_multiply nil Q = nil
    | karatsuba_ofman_multiply P (q::nil) = Polynomial.scalar_multiply P q
    | karatsuba_ofman_multiply (p::nil) Q = Polynomial.scalar_multiply Q p
    | karatsuba_ofman_multiply P Q =
      if (Polynomial.length P) + (Polynomial.length Q) < 4000
      then
          Polynomial.multiply P Q
      else
          let
              val n = Polynomial.length P;
              val m = Polynomial.length Q;
              val s = Polynomial.best_split n m;
              val (T, U) = carve P s;
              val (V, W) = carve Q s;
              val TV = karatsuba_ofman_multiply T V;
              val UW = karatsuba_ofman_multiply U W;
              val TUVW = karatsuba_ofman_multiply (Polynomial.add T U) (Polynomial.add V W);
              val middle = Polynomial.substract (Polynomial.substract TUVW TV) UW;
          in
              Polynomial.add
                  (Polynomial.add
                       TV
                       (Polynomial.shift middle s))
                  (Polynomial.shift UW (2*s))
          end;
#+end_src

** 3.6.3 - eval with value for x

#+begin_src sml
  structure Polynomial = struct
      type CoefficientsList = real list;
      exception UnsuitablePolynomial;

      fun add P nil = P
        | add nil Q = Q
        | add ((p:real)::ps) (q::qs) =
          (p + q) :: (add ps qs);

      fun scalar_multiply nil scalar = nil
        | scalar_multiply ((p:real)::ps) scalar =
          (p * scalar) :: (scalar_multiply ps scalar);

      (* The coefficients of lowest exponents come first by
      convention. Prepending a 0.0 will move all coefficients
      to positions of coefficients of the next higher
      exponents. *)
      fun shift_increasing P = 0.0 :: P;

      fun shift P 0 = P
        | shift P n = shift_increasing (shift P (n - 1));

      fun multiply P nil = nil
        | multiply P (q::qs) =
          add
              (* Start calculating with the coefficient of the
              lowest exponent. At the beginning, this will be
              the coefficient for x^0. For x^0 only the
              coefficient remains, because x^0 = 1. For later
              iterations, the result will be shifted by 1
              position to account for the higher exponent. *)
              (scalar_multiply P q)
              (*

              The next iteration will create a result for the
              next higher exponent. This fact is taken into
              account here, by shifting the result of the
              recursive call by 1 position, before adding it
              to the complete result of the computation.

              At each iteration, we increase the shift by 1,
              which makes sense, because the list of
              coefficients representing a polynomial is
              complete from lowest exponent position to
              highest exponent position. For example when we
              multiply with the coefficient of x^1, the shift
              will be 1. Then when we multiply with the
              coefficient of x^2 the result will be shifted by
              2. As a result we get the coefficients at the
              correct positions.

              ,*)
              (shift_increasing
                   (* Calculate the result for the coefficient
                   of the next exponent. *)
                   (multiply P qs));

      fun substract P nil = P
        | substract P Q =
          add P (scalar_multiply Q ~1.0);

      fun length P = List.length P;

      fun eval nil x = raise UnsuitablePolynomial
        | eval P (x:real) =
          let
              fun iter (nil, x, exponent: int) = 0.0
                | iter ((p::ps), x, exponent: int) =
                  (p * Math.pow(x, (Real.fromInt exponent))) + iter(ps, x, (exponent + 1));
          in
              iter (P, x, 0)
          end;
  end;
#+end_src

** 3.6.4 - Polynomial roots

Given a list of coefficients, the polynomial is searched, which is the product of (x - coeff) for each coefficient. I do not understand why that product is the polynomial, whose root the polynomial of those coefficients is. Would not a "root" mean, that the resulting polynomial divided by one of the roots results in exactly the root again? As in square root of a polynomial? Perhaps the word "root" is used in a different sense here? Anyway, the book already gives the solution of how to calculate the "root" and that is what is implemented in the following:

#+begin_src sml
  fun from_roots nil = 1.0
    | from_roots (root::roots) =
      (* Starting from lowest exponent of x, so the scalar is x^0 and x
      is x^1, which means the substracted coefficient comes first. *)
      Polynomial.multiply [~root, 1.0] (from_roots roots);
#+end_src

** 3.6.5 - Polynomials of Polynomials

This is about using polynomials of another variable (for example y) as coefficients for a polynomial (for example of x). For example:

1 + 2xy + 3xy^2 4(x^3)y

. This term can be written to make it easier to see the coefficients:

   1 + 2xy + 3xy^2 + 4(x^3)y
= +1 + 2xy + 3xy^2 + 4(x^3)y              | adding the + sign
= +1      + 2    xy + 3    xy^2 + 4(x^3)y | adding space for alignment
= +1(x^0) + 2(x^1)y + 3(x^1)y^2 + 4(x^3)y | adding x^n to make coefficients for the same exponents better visible

Now the polynomials of y become visible:

At position x^0: +1(x^0)

-> We are looking for a polynomial of "y", which results in a term with no more "y" in it.

-> ay^0 would result in a mere number.

-> ay^0 with value for "a" must result in 1.
   Any value ^0 is 1, so that 1 needs to be multiplied with 1 to result in a 1.

-> The coefficient then is represented by: ~[1.0]~.

At position x^1: + 2(x^1)y + 3(x^1)y^2

-> We can take the x^1 outside: x^1 * (+2y +3y^2). The "y" containing term can be written completely as:

0y^0 + 2y^1 + 3y^2

-> The coefficient then is represented by: ~[0.0, 2.0, 3.0]~.

At position x^2: no term.

-> The coefficient then is represented by: ~[]~.

At position x^3: +4(x^3)y

The "y" containing term is +4y. It can be written completely as:

0y^0 +4y^1

-> The coefficient then is represented by: ~[0.0, 4.0]~.

#+begin_src sml
  structure PolyPolynomial = struct
      type CoeffList = real list;
      type CoeffListList = CoeffList list;
      exception UnsuitablePolyPolynomial;

      fun add nil nil = nil
        | add (PP: CoeffListList) nil = PP
        | add nil (QQ: CoeffListList) = QQ
        | add ((P:CoeffList)::Ps) ((Q:CoeffList)::Qs) =
          (Polynomial.add P Q) :: (add Ps Qs);

      (* Multiply a poly-polynomial with a polynomial. It is the
      corresponding function to scalar multiplication for
      polynomials. *)

      fun polynomial_multiply nil polynomial = nil
          | polynomial_multiply (P::Ps) polynomial =
            (Polynomial.multiply P polynomial) :: (polynomial_multiply Ps polynomial);

      (* Corresponding function to shift_increasing of
      Polynomial. Instead of shifting by prepending a 0.0 to a list, we
      shift by prepending nil, a list, to the list of lists of
      coefficients.*)

      fun shift_increasing PP = [] :: PP;

      (* The function multiply is the same as multiply for
      polynomials. Except that everything is one abstraction layer
      higher. Instead of multiplying with a number as a coefficient, we multiply with *)

      fun multiply nil nil = nil
        | multiply PP nil = nil
        | multiply nil QQ = nil
        | multiply PP (Q::Qs) =
          add
              (polynomial_multiply PP Q)
              (shift_increasing (multiply PP Qs));
  end;
#+end_src

* TODO 4.



* Other code
:PROPERTIES:
:CUSTOM_ID: other-code
:END:

Perhaps this code should be put in a separate module.

** n choose k - summing smaller problems

#+begin_src sml
open IntInf;

fun n_choose_k (n: int, 1) = n
  | n_choose_k (n: int, k: int) =
    let
        fun iter (n: int, k: int) =
            if k = 0 orelse n = k
            then 1
            else
                (* the number of possibilities without choosing one of the n
                   elements *)
                iter (n - 1, k)
                +
                (* the number of possibilities with choosing one of the n
                   elements *)
                iter (n - 1, k - 1);
    in
        if n >= k
        then
            iter (n, k)
        else
            raise Fail "n must be greater than or equal to k"
    end;
#+end_src

** n choose k

#+begin_src sml
open IntInf;

fun n_choose_k (n: int, k: int) =
    let
        fun fac 0 = 1
          | fac 1 = 1
          | fac n =
            let
                fun iter 1 prod = prod
                  | iter remaining_factors prod =
                    iter (remaining_factors - 1) (prod * remaining_factors);
            in
                if n > 0
                then iter n 1
                else raise Fail "n must be 0 or greater"
            end;
    in
        (fac n) div ((fac (n - k)) * (fac k))
    end;
#+end_src

** reverse list

#+begin_src sml
fun reverse L =
    let
        fun iter (nil, M) = M
          | iter (x::xs, ys) = iter (xs, x::ys)
    in
        iter (L, nil)
    end;
#+end_src

** Printing

#+begin_src sml
  fun print_list elem_2_str lst =
      let
          fun iter remaining_lst =
              if (null remaining_lst)
              then print ""
              else
                  let
                      val _ = print (elem_2_str (hd remaining_lst));
                      val _ = print "\n";
                  in
                      iter (tl remaining_lst)
                  end;
      in
          iter lst
      end;

  print_list Int.toString [1,2,3,4]
#+end_src
